#pragma once

#include<iostream>
#include<vector>
#include<queue>
using std::vector;
using std::priority_queue;

template<class W>
struct HuffmanNode
{
	HuffmanNode(const W& weight = W())
		:_weight(weight)
		, _pleft(nullptr), _pright(nullptr), _pparent(nullptr)
	{}
	W _weight;
	HuffmanNode<W>* _pleft;
	HuffmanNode<W>* _pright;
	HuffmanNode<W>* _pparent;
};

//template<class W>
//struct _greater
//{
//	bool operator()(HuffmanNode<W>* const& left, HuffmanNode<W>* const& right)
//	{
//		return left->_weight > right->_weight;
//	}
//};

template<class W>
class HuffmanTree
{
	typedef HuffmanNode<W>* pNode;
	typedef HuffmanNode<W> Node;

	struct _greater
	{
		bool operator()(pNode left, pNode right)
		{
			return left->_weight > right->_weight;
		}
	};

public:
	HuffmanTree()
		:_proot(nullptr)//, _leaves(0)
	{}

	HuffmanTree(const vector<W>& DataSource, const W& invalid)
	{
		priority_queue<pNode, vector<pNode>, _greater> HuffmanForest;
		for (auto e : DataSource)
		{
			if (e != invalid)
			{
				pNode pNewNode = new Node(e);
				HuffmanForest.push(pNewNode);
			}
		}
		//_leaves = HuffmanForest.size();

		while (!HuffmanForest.empty())
		{
			pNode pleft = HuffmanForest.top();
			HuffmanForest.pop();
			pNode pright = HuffmanForest.top();
			HuffmanForest.pop();

			pNode pNewNode = new Node(pleft->_weight + pright->_weight);
			pNewNode->_pleft = pleft;
			pleft->_pparent = pNewNode;
			pNewNode->_pright = pright;
			pright->_pparent = pNewNode;

			if (HuffmanForest.empty())
			{
				_proot = pNewNode;
				break;
			}

			HuffmanForest.push(pNewNode);
		}
	}

	pNode GetProot()
	{
		return _proot;
	}

	//size_t GetLeaves()
	//{
	//	return _leaves;
	//}

	~HuffmanTree()
	{
		//std::cout << "~HuffmanTree" << std::endl;
		Destroy(_proot);
	}

private:
	void Destroy(pNode& proot)
	{
		if (proot == nullptr)
			return;
		Destroy(proot->_pleft);
		Destroy(proot->_pright);
		delete proot;
		proot = nullptr;
	}

	pNode _proot = nullptr;
	//size_t _leaves = 0;
};